package leetcode.dp;

/**
 * @author mazouri
 * @create 2021-12-27 19:05
 */
public class _115_numDistinct {
    char[] sc;
    char[] tc;

    public int numDistinct(String s, String t) {
        this.sc = s.toCharArray();
        this.tc = t.toCharArray();

        return helper(sc.length - 1, tc.length - 1);
    }

    private int helper(int i, int j) {
        //t空串，s不是空串 s串什么都不选择 顺序不能颠倒
        if (j < 0) return 1;
        if (i < 0) return 0;

        if (sc[i] == tc[j]) return helper(i - 1, j) + helper(i - 1, j - 1);
        else return helper(i-1,j);
    }

    public static void main(String[] args) {
        System.out.println(new _115_numDistinct().numDistinct("babgbag", "bag"));
    }
}
